\chapter{Sekvečné a paralelné riešenie}

V tejto kapitole si popíšeme sekvenčný a paralelný prístup so samotnou implementáciou.

\section{Sekvenčný algoritmus}

Pri riešení danej úlohy si uvedomme, že potrebujeme prejsť celý priestor, resp. vyskúšať všetky permutácie a ku každej spočítať dilatáciu. Program sa skladá z hlavných častí a to: načítanie grafu zo súboru, vybudovaní asociatívneho kontajnera --- mapy (pôvodne myšlienka vybudovania hashovacej mapy, ale vzhľadom na nemožnosť kompilovať \textit{C++} program s novším štandardom \textit{C++11} sa táto možnosť zamietla, aj keď by viedla k urýchleniu výpočtu) a získania samotnej dilatácie grafu.

Priebeh získania samotnej dilatácie grafu sa dá zjednodušiť nasledujúcim popisom algoritmu:

\begin{algorithm}[H]
	\SetAlgoLined
	\caption{Získanie dilatácie grafu $G$} \label{seq_alg}
		Nech $G$ je graf, $n$ je počet uzlov, $dilatation = INT\_MAX$ je výsledná dilatácia\;
		$\o\left(G\right) = getGraphsDiameter\left(G\right)$\;
		$d = getLowerBound\left(\right)$\;
		$p = getFirstPermutation(n)$\;
		$dilatation = improveDilatation\left(p, dilatation, n \right)$\;
		\While {$p = next\_permutation(p, n)$}{
			$dilatation$ = $improveDilatation\left(p, dilatation, n \right)$\;
			\If{$dilatation$ == $d$} {
				break\;
			}		
		}
\end{algorithm}

\section{Paralelný algoritmus}

Implementácia paralelného algoritmu zachovala pôvodnú implementáciu. Rozšírila sa len o príkazy z \textit{MPI} knižnice a ešte o funkciu $computeDistributions$, ktorá na základe počtu procesorov, počiatočnej permutácie, počtu permutácií, ktoré sa majú skontrolovať, počtu permutácií, ktoré sa už skontrolvali, nám vráti vektor objektov $Distributions$, ktoré pre každý procesor s daným \textit{ID} priradí poradové číslo permutácie a počet, pre koľko permutácií má vypočítať dilatáciu konkrétnej permutácie. 

Začiatok algoritmu je špecifický tým, že v prvom kroku procesor s \textit{ID = 0} rozdelil všetky permutácie medzi ostatné procesory a rozoslal im správu obsahujúcu pole $message$, ktorej prvky obsahovali hodnoty počiatočnej permutácie a počet permutácii, ktoré majú jednotlivé procesory prejsť.

Potom, čo všetky procesory prijmú správu po prvom rozdelení úloh, sa dostávajú do jadra výpočtu, kedy prechádzajú jednotlivé permutácie. Až nejaký procesor prejde všetky svoje permutácie, pošle správu typu \textit{MSG\_WORK\_REQUEST} ostatným procesorom.

Každý procesor po určitej dobe kontroluje, či mu neprišla správa a spracováva správy nasledujúcich typov:
\begin{description}
\item[MSG\_WORK\_REQUEST] \hfill \\
Po prijatí tejto správy bud odošle rozdelenie pre seba a procesory, ktoré túto správu rozoslali.
\item[MSG\_WORK\_SENT] \hfill \\
Procesor si aktualizuje hodnoty poradového čísla počiatočnej permutácie a čísla počtu permutácií, ktoré má spracovať a touto aktualizáciou bude výpočet pokračovať
\item[MSG\_WORK\_NOWORK] \hfill \\
Procesor už nemá čo počítať (všetky permutácie už boli prejdené), vychádza sa z hlavného $while$ cyklu a ukončuje výpočet.
\item[MSG\_FINISH] \hfill \\
Táto správa je prijatá v prípade, ak sa našla dilatácia permutácie, ktorá sa rovná dolnej hranici a teda všetky procesory môžu výpočet ukončiť.
\end{description}

V hlavnom $while$ cykle, kde procesory čakajú na správu, resp. prechádzajú jednotlivé permutácie, sa uchováva zdieľané pole $requests$, v ktorom sa uchovávajú nuly alebo jednotky. Ak je na pozícii $i$ jednotka, znamená to, že procesor s \textit{ID = i} žiada prácu a teda odoslal aj správu typu \textit{MSG\_WORK\_REQUEST}. Po jej prijatí a odoslaní informácií sa vykoná \textit{requests[i] = 0}.

Na odoslanie informácií o novej počiatočnej permutácii a počtu permtácií, ktoré sa majú spracovať, slúži pole $distribs$. Podotknime, že permutácie sa rozdeľujú rovnomerne medzi procesory, ktoré si o prácu žiadajú.